﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProgrammingIsMyPassion.Coding
{
    public class SearchStringinTextProblem
    {
        //problem 
        //Search string s in text t
        //s: char by char
        //S2 execlude chars from t that not available at s
        //s3: BoyerMoore Algorithm
        String text = "xUnit.net is a free, open source, community-focused unit testing tool for the .NET Framework. Written by the original inventor of NUnit v2, xUnit.net is the latest technology for unit testing C#, F#, VB.NET and other .NET languages. xUnit.net works with ReSharper, CodeRush, TestDriven.NET and Xamarin. It is part of the ASP.NET Open Source Gallery under the Outercurve Foundation, licensed under Apache 2 (an OSI approved license). ";
        public string Text
        {
            get
            {
                return text;
            }
            set
            {
                text = value;
            }
        }

        public string Search = "free";

        public int Find1(string t, string s)
        {
            for (int i = 0; i < t.Length; i++)
            {
                bool isexact = true;
                for (int k = 0; k < s.Length; k++)
                {
                    if (s[k] == t[i])
                    {
                        i++;
                        continue;
                    }
                    else
                    {
                        isexact = false;
                        break;
                    }
                }
                if (isexact == false) continue;
                else
                    return i - s.Length;
            }
            return -1;
        }

        private Dictionary<Char, int> BoyerMooreTable(string pattern)
        {
            var badmatch = new Dictionary<char, int>();
            for (int i = 0; i < pattern.Length; i++)
            {
                int idx = Math.Max(1, pattern.Length - i - 1);
                if (badmatch.ContainsKey(pattern[i]) == false)
                    badmatch.Add(pattern[i], idx);
                else
                    badmatch[pattern[i]] = idx;

            }
            badmatch.Add('*', pattern.Length);
            return badmatch;
        }
        public int Find2_BoyerMoore(string t, string s)
        {
            var badmatch = BoyerMooreTable(s);
            int i = s.Length - 1;

            while (i < t.Length)
            {
                int originali = i;
                int increase_Idx_By = 0;
                bool isexact = true;
                for (int k = s.Length - 1; k >= 0; k--)
                {
                    if (s[k] == t[i])
                    {
                        i--;
                        continue;
                    }
                    else
                    {
                        isexact = false;
                        if (badmatch.ContainsKey(t[i]))
                            increase_Idx_By = badmatch[t[i]];
                        else
                            increase_Idx_By = s.Length;
                        break;
                    }
                }
                if (isexact == false)
                {
                    i = originali + increase_Idx_By;
                }
                else
                    return i + 1;
            }
            return -1;

        }

        #region redo boyer-Moore
        private Dictionary<char, int> BooyerTable(String pattern)
        {
            var length = pattern.Length;
            Dictionary<char, int> table = new Dictionary<char, int>();
            for (int i = 0; i < length; i++)
            {
                var key = pattern[i];
                if (table.ContainsKey(key) == false)
                    table.Add(key, 0);
                table[key] = Math.Max(1, length - i - 1);
            }
            table.Add('*', length);
            return table;
        }
        public int QuickTextSearch(String t, string s)
        {
            var indexTable = BooyerTable(s);
            int tlength = t.Length;
            int sLength = s.Length;
            int i = s.Length - 1;
            int moveBy = 0;
            while (i < tlength)
            {
                int currenti = i;
                int k = sLength -1;
                while(k >= 0)
                {
                    if (t[currenti] == s[k])
                    {
                        currenti--;
                        k--;
                    }
                    else
                    {
                        if (indexTable.ContainsKey(t[currenti]))
                            moveBy = indexTable[t[currenti]];
                        else
                            moveBy = sLength;
                        break;
                    }
                }
                if (k >= 0)
                {
                    i += moveBy;
                }
                else
                    return i - sLength - 1;
            }
            return -1;
        }
        #endregion
    }
}
